package org.apache.commons.graph.algorithms.coloring

import org.apache.commons.graph.UndirectedGraph
import org.apache.commons.graph.algorithms.coloring.exception.NotEnoughColorsException
import org.apache.commons.graph.algorithms.coloring.internal.UncoloredOrderedVertices

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/


/**
 * Builder for selecting the coloring algorithm to perform.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
 * @param <C> the Color vertices type
</C></E></V> */
interface ColoringAlgorithmsSelector<V, E, C> {
    /**
     * Graph m-coloring algorithm. This algorithm uses a brute-force backtracking
     * procedure to find a graph color.
     *
     * @return The color - vertex association.
     */
    fun applyingBackTrackingAlgorithm(): ColoredVertices<V, C>

    /**
     * Graph m-coloring algorithm. This algorithm uses a brute-force backtracking
     * procedure to find a graph color using a predefined set of colors.
     *
     * @param partialColoredVertex subset of vertices already colored.
     * @return The color - vertex association.
     */
    fun applyingBackTrackingAlgorithm(partialColoredVertex: ColoredVertices<V, C>): ColoredVertices<V, C>

    /**
     * Colors the graph such that no two adjacent vertices share the same color.
     *
     * @return The color - vertex association.
     */
    fun applyingGreedyAlgorithm(): ColoredVertices<V, C>
}


/**
 * [ColoringAlgorithmsSelector] implementation.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
 * @param <C> the Color vertices type
</C></E></V> */
internal class DefaultColoringAlgorithmsSelector<V, E, C>(
    private val g: UndirectedGraph<V, E>,
    private val colors: Set<C>
) : ColoringAlgorithmsSelector<V, E, C> {

    /**
     * {@inheritDoc}
     */
    override fun applyingBackTrackingAlgorithm(): ColoredVertices<V, C> {
        return applyingBackTrackingAlgorithm(ColoredVertices())
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingBackTrackingAlgorithm(partialColoredVertex: ColoredVertices<V, C>): ColoredVertices<V, C> {
        //var partialColoredVertex = partialColoredVertex
        //partialColoredVertex = Assertions.checkNotNull(partialColoredVertex, "PartialColoredVertex must be not null")

        val verticesList: MutableList<V> = ArrayList()

        for (v in g.vertices) {
            if (!partialColoredVertex.containsColoredVertex(v)) {
                verticesList.add(v)
            }
        }

        if (backtraking(-1, verticesList, partialColoredVertex)) {
            return partialColoredVertex
        }

        throw NotEnoughColorsException(colors)
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingGreedyAlgorithm(): ColoredVertices<V, C> {
        val coloredVertices = ColoredVertices<V, C>()

        // decreasing sorting all vertices by degree.
        val uncoloredOrderedVertices = UncoloredOrderedVertices<V>()

        for (v in g.vertices) {
            uncoloredOrderedVertices.addVertexDegree(v, g.getDegree(v))
        }

        // search coloring
        var it: Iterator<V> = uncoloredOrderedVertices.iterator()
        val colorsIt = colors.iterator()
        while (it.hasNext()) {
            if (!colorsIt.hasNext()) {
                throw NotEnoughColorsException(colors)
            }
            val color: C = colorsIt.next()

            // this list contains all vertex colors with the current color.
            val currentColorVertices: MutableList<V> = ArrayList()
            val uncoloredVtxIterator = uncoloredOrderedVertices.iterator()
            while (uncoloredVtxIterator.hasNext()) {
                val uncoloredVtx = uncoloredVtxIterator.next()

                var foundAnAdjacentVertex = false
                for (currentColoredVtx in currentColorVertices) {
                    if (g.getEdge(currentColoredVtx, uncoloredVtx) != null) {
                        // we've found that 'uncoloredVtx' is adiacent to
                        // 'currentColoredVtx'
                        foundAnAdjacentVertex = true
                        break
                    }
                }

                if (!foundAnAdjacentVertex) {
                    // It's possible to color the vertex 'uncoloredVtx', it has
                    // no connected vertex into
                    // 'currentcoloredvtx'
                    uncoloredVtxIterator.remove()
                    coloredVertices.addColor(uncoloredVtx, color)
                    currentColorVertices.add(uncoloredVtx)
                }
            }

            it = uncoloredOrderedVertices.iterator()
        }

        return coloredVertices
    }

    /**
     * This is the recursive step.
     *
     * @param result The set that will be returned
     * @param element the element
     * @return true if there is a valid coloring for the graph, false otherwise.
     */
    private fun backtraking(
        currentVertexIndex: Int,
        verticesList: List<V>,
        coloredVertices: ColoredVertices<V, C>
    ): Boolean {
        if (currentVertexIndex != -1 && isThereColorConflict(verticesList[currentVertexIndex], coloredVertices)) {
            return false
        }

        if (currentVertexIndex == verticesList.size - 1) {
            return true
        }

        val next = currentVertexIndex + 1
        val nextVertex = verticesList[next]
        for (color in colors) {
            coloredVertices.addColor(nextVertex, color)
            val isDone = backtraking(next, verticesList, coloredVertices)
            if (isDone) {
                return true
            }
        }
        coloredVertices.removeColor(nextVertex)
        return false
    }

    /**
     * Tests if there is some adjacent vertices with the same color.
     *
     * @param currentVertex
     * @return
     */
    private fun isThereColorConflict(currentVertex: V?, coloredVertices: ColoredVertices<V, C>): Boolean {
        if (currentVertex == null) {
            return false
        }
        val nextVertecColor = coloredVertices.getColor(currentVertex) ?: return false

        for (abj in g.getConnectedVertices(currentVertex)) {
            val adjColor = coloredVertices.getColor(abj)
            if (adjColor != null && nextVertecColor == adjColor) {
                return true
            }
        }
        return false
    }
}
